package com.example.leetcode.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author haitao
 * @date 2022/1/11 10:29 上午
 * 求两个list的交集
 * 1.set方式求解。空间复杂度m+n，时间复杂度m+n
 * 2.排序+双指针算法 时间复杂度mlogm+nlogn
 */
public class Solution349 {


    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> list = new ArrayList<>();
        int index1 = 0, index2 = 0;
        while (index1 < nums1.length && index2 < nums2.length) {
            int num1 = nums1[index1];
            int num2 = nums2[index2];
            if (num1 == num2) {
                if (list.size() == 0 || list.get(list.size() - 1) != num1) {
                    list.add(num1);
                }
                index1++;
                index2++;
            } else if (num1 > num2) {
                index2++;
            } else {
                index1++;
            }
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }


    public static void main(String[] args) {
        Solution349 solution349 = new Solution349();
        int[] nums1 = new int[]{1, 2, 3};
        int[] nums2 = new int[]{3, 5, 6};
        System.out.println(Arrays.toString(solution349.intersection(nums1, nums2)));

    }
}
